package com.tgy.leetcode.slowfastpointer;

import com.tgy.leetcode.ListNode;

/**
 * @Author: tgy
 * @Date: 12/22/20 2:22 PM
 */
public class SlowFastPointer_01 {

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * @param root
     * @return
     */
    public static ListNode findBeforeCenter(ListNode root) {

        if (root == null) {

            return null;
        }

        ListNode slow = root,fast = root;

        while (fast != null && fast.getNext() != null && fast.getNext().getNext() != null) {

            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }

        return slow;
    }

    /**
     * 2)输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * @param root
     * @return
     */
    public static ListNode findAfterCenter(ListNode root) {

        if (root == null) {

            return null;
        }

        ListNode slow = root,fast = root;

        while (fast != null && fast.getNext() != null) {

            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }

        return slow;
    }

    /**
     * 3)输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个图。
     * @param root
     * @return
     */
    public static ListNode findBBCenter(ListNode root) {

        if (root == null || root.getNext() == null || root.getNext().getNext() == null) {

            return null;
        }



        ListNode slow = root,fast = root.getNext().getNext();

        while (fast != null && fast.getNext() != null && fast.getNext().getNext() != null) {

            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }

        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     * @param root
     * @return
     */
    public static ListNode findAACenter(ListNode root) {

        if (root == null || root.getNext() == null) {

            return null;
        }

        if (root.getNext().getNext() == null) {

            return root.getNext();
        }


        ListNode slow = root,fast = root.getNext().getNext();

        while (fast != null && fast.getNext() != null) {

            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }


        return slow;
    }
}
